package com.zklh.leetcode.top100;

import com.zklh.leetcode.structure.monotonestack.DailyTemperatures;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

/**
 * 每日温度算法实现
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2022/3/18 10:04
 */
public class Solution739 {
    /**
     * 给定一个温度, 返回一个每个当前天 需要等多少天才能等到一个更温暖的温度的数组, 如果等不到返回0
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures){
        // 存储结果
        int[] result = new int[temperatures.length];
        // 存储nums[i] 后所有元素的压缩结果, 去掉波谷, 只保留波峰节点, 这里stack中存储的是索引
        LinkedList<Integer> stack = new LinkedList<>();

        for (int i = temperatures.length-1; i >= 0; i--) {
            // 先根据nums[i] 作为stack的顶层元素, 把stack压缩, 压缩原则就是去掉波谷, 保留波峰
            while (!stack.isEmpty() && temperatures[stack.getFirst()] <= temperatures[i]) {
                stack.removeFirst();
            }
            // 当前i 是否有挡板取决于当前 的stack 情况, 只要有剩余节点, 就是有挡板的
            result[i] = stack.isEmpty() ? 0 : stack.getFirst()-i;
            // 将当前节点作为stack顶层
            stack.addFirst(i);
        }

        return result;
    }

    public static void main(String[] args) {
        DailyTemperatures dailyTemperatures = new DailyTemperatures();
        System.out.println(Arrays.toString(dailyTemperatures.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 76})));
    }

}
